package work.xiaohong.arithmetic.SortArithmetic;

/**
 * @author xiaohong
 * @version 1.0
 * @date 2021/10/26 0026 10:52
 * @description 选择排序
 */
public class Selection {

    /**
     * 排序原理
     * 1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，
     * 如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
     * 2.交换第一个索引处和最小值所在的索引处的值
     *
     * 时间复杂度
     * 数据比较次数
     * （N-1）+(N-2)+(N-3)+...+2+1 = N^2/2-N/2
     * 数据交换次数
     * N-1
     * 时间复杂度O(N^2)
     *
     * 不稳定的排序算法
     */

    public static void selectSort(Comparable[] arr){

        for (int i = 0; i < arr.length-2; i++) { // 每次需要进行比较的元素个数，最后剩下一个不需要比较
            // 最小元素的索引，默认认为是第一个元素
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if (SortUtils.greater(arr[minIndex],arr[j])){
                    // 更换最小索引下标
                    minIndex = j;
                }
            }

            // 将找到的最小索引替换到本次遍历元素列表的开头
            SortUtils.swap(arr,i,minIndex);

        }
    }

}
